{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Reorganize String"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #greedy #hash-table #string #counting #sorting #heap-priority-queue"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #贪心 #哈希表 #字符串 #计数 #排序 #堆（优先队列）"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: reorganizeString"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #重构字符串"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给定一个字符串&nbsp;<code>s</code>&nbsp;，检查是否能重新排布其中的字母，使得两相邻的字符不同。</p>\n",
    "\n",
    "<p>返回<em> <code>s</code>&nbsp;的任意可能的重新排列。若不可行，返回空字符串&nbsp;<code>\"\"</code></em>&nbsp;。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例&nbsp;1:</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入:</strong> s = \"aab\"\n",
    "<strong>输出:</strong> \"aba\"\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2:</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入:</strong> s = \"aaab\"\n",
    "<strong>输出:</strong> \"\"\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示:</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= s.length &lt;= 500</code></li>\n",
    "\t<li><code>s</code> 只包含小写字母</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [reorganize-string](https://leetcode.cn/problems/reorganize-string/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [reorganize-string](https://leetcode.cn/problems/reorganize-string/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['\"aab\"', '\"aaab\"']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import Counter, defaultdict\n",
    "\n",
    "class Solution:\n",
    "  def reorganizeString(self, S):\n",
    "    \"\"\"\n",
    "    :type S: str\n",
    "    :rtype: str\n",
    "    \"\"\"\n",
    "    count = Counter( S )\n",
    "\n",
    "    freq = list( count.values() )\n",
    "    if len( freq ) == 1:\n",
    "      return ''\n",
    "\n",
    "    freq.sort( reverse = True )\n",
    "    if max( freq ) > sum( freq[ 1: ] ) + 1:\n",
    "      return ''\n",
    "\n",
    "    occur = defaultdict( list )\n",
    "    for char, n in count.items():\n",
    "      occur[ n ].append( char )\n",
    "\n",
    "    rows, newRow = list(), list()\n",
    "    rowLen = max( freq )\n",
    "\n",
    "    for n in sorted( occur.keys(), reverse = True ):\n",
    "      for char in occur[ n ]:\n",
    "        if len( newRow ) + n >= rowLen:\n",
    "          nUsed = rowLen - len( newRow )\n",
    "          newRow.extend( char * nUsed )\n",
    "          rows.append( newRow )\n",
    "          nLeft = n - nUsed\n",
    "          newRow = list( char * nLeft ) if nLeft > 0 else list()\n",
    "        else:\n",
    "          newRow.extend( char * n )\n",
    "    if len( newRow ) > 0:\n",
    "      rows.append( newRow[:] )\n",
    "\n",
    "    k = len( rows[ -1 ] )\n",
    "    A = [ ''.join( rows[ r ][ c ] for r in range( len( rows ) ) )\n",
    "          for c in range( k ) ]\n",
    "    A.extend( ''.join( rows[ r ][ c ] for r in range( len( rows ) - 1 ) )\n",
    "              for c in range( k, rowLen ) )\n",
    "\n",
    "    return ''.join( A )\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reorganizeString(self, s):\n",
    "        \"\"\"\n",
    "        :type s: str\n",
    "        :rtype: str\n",
    "        \"\"\"\n",
    "        words = [0 for x in range(26)]\n",
    "        inta = ord('a')\n",
    "        for each in s:\n",
    "            words[ord(each) - inta] += 1\n",
    "        maxTime = max(words)\n",
    "        maxIndex = words.index(maxTime)\n",
    "        maxWord = chr(maxIndex + inta)\n",
    "        words[maxIndex] = 0\n",
    "        import math\n",
    "        if maxTime > math.ceil(len(s) / 2):\n",
    "            return ''\n",
    "        chrList = [maxWord for x in range(len(s))]\n",
    "        insert = maxTime * 2\n",
    "        for i in range(26):\n",
    "            count = words[i]\n",
    "            while count > 0:\n",
    "                if insert >= len(s):\n",
    "                    insert = 1\n",
    "                chrList[insert] = chr(i + inta)\n",
    "                insert += 2\n",
    "                count -= 1\n",
    "        return ''.join(chrList)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reorganizeString(self, S):\n",
    "        \"\"\"\n",
    "        :type S: str\n",
    "        :rtype: str\n",
    "        \"\"\"\n",
    "        if not S:\n",
    "            return ''\n",
    "        c = collections.Counter(S)\n",
    "        arr = c.most_common()\n",
    "        if arr[0][1] > (len(S) + 1) // 2:\n",
    "            return ''\n",
    "        res = [''] * len(S)\n",
    "        i = 0\n",
    "        for c, n in arr:\n",
    "            while n > 0:\n",
    "                res[i] = c\n",
    "                i += 2\n",
    "                n -= 1\n",
    "                if i >= len(res):\n",
    "                    i = 1\n",
    "        return ''.join(res)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import queue\n",
    "class Solution:\n",
    "    def reorganizeString(self, S):\n",
    "        \"\"\"\n",
    "        :type S: str\n",
    "        :rtype: str\n",
    "        \"\"\"\n",
    "        res=\"\"\n",
    "        n=len(S)\n",
    "        a=[0 for i in range(26)]\n",
    "        for i in range(n):\n",
    "            a[ord(S[i])-ord('a')]+=1\n",
    "        for i in range(26):\n",
    "            if a[i]>(n+1)//2:\n",
    "                return res\n",
    "        que=queue.PriorityQueue()\n",
    "        for i in range(26):\n",
    "            if(a[i]>0):\n",
    "                que.put([-a[i],chr(i+ord('a'))])\n",
    "        while que.qsize()>1:\n",
    "            s1=que.get()\n",
    "            s2=que.get()\n",
    "            res+=s1[1]\n",
    "            res+=s2[1]\n",
    "            if s1[0]<-1:\n",
    "                s1[0]+=1\n",
    "                que.put(s1)\n",
    "            if s2[0]<-1:\n",
    "                s2[0]+=1\n",
    "                que.put(s2)\n",
    "        if que.qsize()>0:\n",
    "            res+=que.get()[1]\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reorganizeString(self, S):\n",
    "        \"\"\"\n",
    "        :type S: str\n",
    "        :rtype: str\n",
    "        \"\"\"\n",
    "        import queue\n",
    "        counter = [0] * 26\n",
    "        for s in S:\n",
    "            counter[ord(s) - 97] += 1\n",
    "        que = queue.PriorityQueue()\n",
    "        n = len(S)\n",
    "        for i in range(26):\n",
    "            if counter[i] > 0:\n",
    "                if counter[i] > (n + 1) // 2:\n",
    "                    return ''\n",
    "                que.put(-(counter[i] * 100 + i))\n",
    "        res = []\n",
    "        while que.qsize() > 1:\n",
    "            first = -que.get()\n",
    "            second = -que.get()\n",
    "            res.append(chr(first % 100 + 97))\n",
    "            res.append(chr(second % 100 + 97))\n",
    "            if first // 100 > 1:\n",
    "                que.put(100-first)\n",
    "            if second // 100 > 1:\n",
    "                que.put(100-second)\n",
    "        if que.qsize() > 0:\n",
    "            res.append(chr(-que.get() % 100 + 97))\n",
    "        return ''.join(res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from heapq import heappush, heappop, heapify\n",
    "class Solution:\n",
    "    def reorganizeString(self, S: str) -> str:\n",
    "        N = len(S)\n",
    "        half = (N + 1) // 2\n",
    "        counter = {}\n",
    "        for c in S:\n",
    "            counter[c] = counter.get(c, 0) + 1\n",
    "            if counter[c] > half:\n",
    "                return ''\n",
    "        heap = [(-freq, c) for c, freq in counter.items()]\n",
    "        heapify(heap)\n",
    "        result = []\n",
    "        while len(heap) >= 2:\n",
    "            first = heappop(heap)\n",
    "            second = heappop(heap)\n",
    "            result.append(first[1])\n",
    "            result.append(second[1])\n",
    "            if first[0] + 1:\n",
    "                heappush(heap, (first[0] + 1, first[1]))\n",
    "            if second[0] + 1:\n",
    "                heappush(heap, (second[0] + 1, second[1]))\n",
    "        if heap:\n",
    "            result.append(heap[0][1])\n",
    "        return ''.join(result)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reorganizeString(self, S: str) -> str:\n",
    "        if not S:\n",
    "            return ''\n",
    "        import collections\n",
    "        d=collections.defaultdict(int)\n",
    "        maxcount=0\n",
    "        n=len(S)\n",
    "        for s in S:\n",
    "            d[s]+=1\n",
    "            maxcount=max(maxcount,d[s])\n",
    "        if maxcount>(n+1)//2:\n",
    "            return ''\n",
    "        even,odd=0,1\n",
    "        res=[0]*n\n",
    "        for i in d:\n",
    "            while d[i]>0 and d[i]<n//2+1 and odd<n:\n",
    "                res[odd]=i \n",
    "                odd+=2\n",
    "                d[i]-=1\n",
    "            while d[i]>0:\n",
    "                res[even]=i \n",
    "                even+=2\n",
    "                d[i]-=1\n",
    "        return''.join(res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import Counter\n",
    "class Solution:\n",
    "\tdef reorganizeString(self,S):\n",
    "\t\tcnt,val=Counter(S),sum(divmod(len(S),2))\n",
    "\t\tchar,num=cnt.most_common(1)[0]\n",
    "\t\tif num>val:\n",
    "\t\t\treturn \"\"\n",
    "\t\tdel cnt[char]\n",
    "\t\tt=char*num+\"\".join(i*j for i,j in cnt.items())\n",
    "\t\t#return \"\".join(i+j for i,j in zip_longest(t[:val],t[val:],fillvalue=\"\"))\n",
    "\t\tans=[\"\"]*len(S)\n",
    "\t\tans[::2],ans[1::2]=t[:val],t[val:]\n",
    "\t\treturn \"\".join(ans)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import Counter\n",
    "import math\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def reorganizeString(self, S: str) -> str:\n",
    "        length = len(S)\n",
    "        max_char = S[0]\n",
    "        s_counter = Counter(S)\n",
    "        for k in s_counter:\n",
    "            if s_counter.get(max_char) < s_counter.get(k):\n",
    "                max_char = k\n",
    "        if s_counter.get(max_char) > math.ceil(length / 2):\n",
    "            return \"\"\n",
    "\n",
    "        max_count = s_counter.get(max_char)\n",
    "        res = [[max_char] for _ in range(max_count)]\n",
    "        s_counter.pop(max_char)\n",
    "        wait_c = \"\"\n",
    "        for k in s_counter:\n",
    "            wait_c += k * s_counter.get(k)\n",
    "        wait_c = list(wait_c)\n",
    "        while wait_c:\n",
    "            try:\n",
    "                for i in range(max_count):\n",
    "                    res[i].append(wait_c.pop(0))\n",
    "            except:\n",
    "                break\n",
    "        return \"\".join(list(map(\"\".join, res)))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def reorganizeString(self, S):\n",
    "        N = len(S)\n",
    "        A = []\n",
    "        for c, x in sorted((S.count(x), x) for x in set(S)):\n",
    "            if c > (N+1)/2: return \"\"\n",
    "            A.extend(c * x)\n",
    "        ans = [None] * N\n",
    "        ans[::2] = A[N//2:]\n",
    "        ans[1::2] = A[:N//2]\n",
    "        return \"\".join(ans)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reorganizeString(self, S: str) -> str:\n",
    "        S = list(S)\n",
    "        count = collections.defaultdict(int)\n",
    "        for s in S:\n",
    "            count[s] += 1\n",
    "        if max(count.values()) > (len(S) + 1) / 2:\n",
    "            return ''\n",
    "        keys = list(count.keys())\n",
    "        keys.sort(key=lambda x: count[x], reverse=True)\n",
    "        ss = [k for k in keys for _ in range(count[k])]\n",
    "\n",
    "        start = 0\n",
    "        step = 0\n",
    "        for s in ss:\n",
    "            if start + step * 2 > len(S)-1:\n",
    "                start += 1\n",
    "                step = 0\n",
    "            S[start + step * 2] = s\n",
    "            step += 1\n",
    "        return ''.join(S)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import heapq\n",
    "from collections import Counter\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def reorganizeString(self, S: str) -> str:\n",
    "        if not S:\n",
    "            return ''\n",
    "\n",
    "        s_c = Counter(S)\n",
    "        # 因为python中的是小顶堆，因此这里需要是负数\n",
    "        s_heq = [(-item[1], item[0]) for item in list(s_c.items())]\n",
    "        heapq.heapify(s_heq)\n",
    "\n",
    "        rst = ''\n",
    "        # 这道题的解法适用于任意的间隔，因为这里题目要求是间隔2，所以写死\n",
    "        interval = 2\n",
    "\n",
    "        while s_heq:\n",
    "            chs = []\n",
    "            # 因为是需要间隔xx，所以这里需要遍历xx次，\n",
    "            for i in range(interval):\n",
    "                # 因为堆里面的字符是唯一的，每pop一次就减少一种字符，当堆里面没有字符时，检查是否遍历完了所有的字符\n",
    "                if not s_heq:\n",
    "                    return rst if len(rst) == len(S) else ''\n",
    "\n",
    "                # 这里每次取出来的一定是字符个数最多的字符种类\n",
    "                ch = heapq.heappop(s_heq)[1]\n",
    "                # 使用一个字符，该类型字符个数相应的减一\n",
    "                s_c[ch] -= 1\n",
    "                # 记录pop出来的字符，下面需要重新插入堆中\n",
    "                chs.append(ch)\n",
    "                # 拼接结果\n",
    "                rst += ch\n",
    "\n",
    "            # 将pop出来的字符重新插入堆中\n",
    "            for ch in chs:\n",
    "                # 如果该类型字符个数已使用完，则不再加入\n",
    "                if s_c[ch] > 0:\n",
    "                    heapq.heappush(s_heq, (-s_c[ch], ch))\n",
    "\n",
    "        return rst\n",
    "\n",
    "\n",
    "if __name__ == '__main__':\n",
    "    test = Solution()\n",
    "    print(test.reorganizeString('AAD'))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import heapq\n",
    "from collections import Counter\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def reorganizeString(self, S: str) -> str:\n",
    "        if not S:\n",
    "            return ''\n",
    "\n",
    "        s_c = Counter(S)\n",
    "        # 因为python中的是小顶堆，因此这里需要是负数\n",
    "        s_heq = [(-item[1], item[0]) for item in list(s_c.items())]\n",
    "        heapq.heapify(s_heq)\n",
    "\n",
    "        rst = ''\n",
    "        # 这道题的解法适用于任意的间隔，因为这里题目要求是间隔2，所以写死\n",
    "        interval = 2\n",
    "\n",
    "        while s_heq:\n",
    "            chs = []\n",
    "            # 因为是需要间隔xx，所以这里需要遍历xx次，\n",
    "            for i in range(interval):\n",
    "                # 因为堆里面的字符是唯一的，每pop一次就减少一种字符，当堆里面没有字符时，检查是否遍历完了所有的字符\n",
    "                if not s_heq:\n",
    "                    return rst if len(rst) == len(S) else ''\n",
    "\n",
    "                # 这里每次取出来的一定是字符个数最多的字符种类\n",
    "                ch = heapq.heappop(s_heq)[1]\n",
    "                # 使用一个字符，该类型字符个数相应的减一\n",
    "                s_c[ch] -= 1\n",
    "                # 记录pop出来的字符，下面需要重新插入堆中\n",
    "                chs.append(ch)\n",
    "                # 拼接结果\n",
    "                rst += ch\n",
    "\n",
    "            # 将pop出来的字符重新插入堆中\n",
    "            for ch in chs:\n",
    "                # 如果该类型字符个数已使用完，则不再加入\n",
    "                if s_c[ch] > 0:\n",
    "                    heapq.heappush(s_heq, (-s_c[ch], ch))\n",
    "\n",
    "        return rst\n",
    "\n",
    "\n",
    "if __name__ == '__main__':\n",
    "    test = Solution()\n",
    "    print(test.reorganizeString('AAD'))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# 767. 重构字符串\n",
    "from sortedcontainers import SortedList\n",
    "class Solution:\n",
    "    def reorganizeString(self, S: str) -> str:\n",
    "        if not S: return \"\"\n",
    "        size = len(S)\n",
    "        store = defaultdict(int)\n",
    "        for val in S:\n",
    "            store[val] += 1\n",
    "        ls = SortedList(store.items(), key = lambda p:(p[1]))\n",
    "        if ls[-1][1] > (size+1) // 2: return \"\"\n",
    "\n",
    "        ans = \"\"\n",
    "        while ls:\n",
    "            if not ans:\n",
    "                c, times = ls.pop()\n",
    "                ans += c\n",
    "                if times > 1:\n",
    "                    ls.add((c, times-1))\n",
    "            else:\n",
    "                pos = -1\n",
    "                while ls[pos][0] == ans[-1]:\n",
    "                    pos -= 1\n",
    "                c, times = ls.pop(pos)\n",
    "                ans += c\n",
    "                if times > 1:\n",
    "                    ls.add((c, times-1))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reorganizeString(self, S: str) -> str:\n",
    "        def get_str(list_str, ch):\n",
    "            if list_str[0][1] == 0:\n",
    "                return []\n",
    "            for i in range(len(list_str)):\n",
    "                new_ch = list_str[i][0]\n",
    "                if new_ch == ch:\n",
    "                    continue\n",
    "                if list_str[i][1] == 0:\n",
    "                    return [-1]\n",
    "                else:\n",
    "                    list_str[i][1] -= 1\n",
    "                    new_list = sorted(list_str, key=lambda x:x[1], reverse=True)\n",
    "                    get_list = get_str(new_list, new_ch)\n",
    "                    if get_list and get_list[0] == -1:\n",
    "                        return [-1]\n",
    "                    else:\n",
    "                        return [new_ch] + get_list\n",
    "            return [-1]\n",
    "        if len(S) <= 1:\n",
    "            return S\n",
    "        dict_str = collections.Counter(S)\n",
    "        order_dict = sorted(dict_str.items(), key=lambda x:x[1], reverse=True)\n",
    "        order_dict = [list(x) for x in order_dict]\n",
    "        res = get_str(order_dict, \"\")\n",
    "        if res and res[0] == -1:\n",
    "            return \"\"\n",
    "        else:\n",
    "            return \"\".join(res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reorganizeString(self, s: str) -> str:\n",
    "        if len(s) < 2:\n",
    "            return s\n",
    "        \n",
    "        length = len(s)\n",
    "        counts = collections.Counter(s)\n",
    "        maxCount = max(counts.items(), key=lambda x: x[1])[1]\n",
    "        if maxCount > (length + 1) // 2:\n",
    "            return \"\"\n",
    "        \n",
    "        reorganizeArray = [\"\"] * length\n",
    "        evenIndex, oddIndex = 0, 1\n",
    "        halfLength = length // 2\n",
    "\n",
    "        for c, count in counts.items():\n",
    "            while count > 0 and count <= halfLength and oddIndex < length:\n",
    "                reorganizeArray[oddIndex] = c\n",
    "                count -= 1\n",
    "                oddIndex += 2\n",
    "            while count > 0:\n",
    "                reorganizeArray[evenIndex] = c\n",
    "                count -= 1\n",
    "                evenIndex += 2\n",
    "        \n",
    "        return \"\".join(reorganizeArray)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reorganizeString(self, s: str) -> str:\n",
    "        cnt = {}\n",
    "        for i in s:\n",
    "            if not i in cnt.keys():\n",
    "                cnt[i] = 1\n",
    "            else:\n",
    "                cnt[i]+=1\n",
    "        # bucks_num,mx_chr = max(zip(cnt.values(),cnt.keys()))\n",
    "        cnt = sorted(zip(cnt.values(),cnt.keys()),reverse = True)\n",
    "        bucks_num,_ = cnt[0]\n",
    "        if bucks_num>len(s)-bucks_num+1:\n",
    "            return \"\"\n",
    "        bucks = [cnt[0][1] for _ in range(bucks_num)]\n",
    "        idx = 0\n",
    "        for i in cnt[1:]:\n",
    "            for j in range(i[0]):\n",
    "                bucks[idx]+=i[1]\n",
    "                if idx==bucks_num-1:\n",
    "                    idx=0\n",
    "                else:\n",
    "                    idx+=1\n",
    "        return ''.join(bucks)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reorganizeString(self, s: str) -> str:\n",
    "        from collections import defaultdict\n",
    "        import math\n",
    "        s_dic = defaultdict(int)\n",
    "        for i in s:\n",
    "            s_dic[i] += 1\n",
    "        n = len(s)\n",
    "        r = [0]*n\n",
    "        s_dict_sorted = sorted(s_dic.items(),key = lambda x:x[1],reverse = True)\n",
    "        s_dict_sorted = [[ss[0],ss[1]] for ss in s_dict_sorted]\n",
    "        if s_dict_sorted[0][1] > math.ceil(n/2):\n",
    "            return ''\n",
    "        odd = 0\n",
    "        even = 1\n",
    "        i = 0\n",
    "        while odd < n:\n",
    "            if s_dict_sorted[i][1] == 0:\n",
    "                i += 1\n",
    "            r[odd] = s_dict_sorted[i][0]\n",
    "            s_dict_sorted[i][1] -= 1\n",
    "            odd += 2\n",
    "        while even < n:\n",
    "            if s_dict_sorted[i][1] == 0:\n",
    "                i += 1\n",
    "            r[even] = s_dict_sorted[i][0]\n",
    "            s_dict_sorted[i][1] -= 1\n",
    "            even += 2\n",
    "        return ''.join(r)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reorganizeString(self, s: str) -> str:\n",
    "        if len(s) == 1:return s\n",
    "        dic = {}\n",
    "        n = len(s)\n",
    "        for c in s:\n",
    "            if c not in dic:\n",
    "                dic[c] = 0\n",
    "            dic[c] += 1\n",
    "        ans = \"\"\n",
    "        l = list(dic.items())\n",
    "        ll = sorted(l,key = lambda x:x[1],reverse = True)\n",
    "        for i in range(len(ll)):\n",
    "            ll[i] = list(ll[i])\n",
    "        while sum([x[1]>0 for x in ll]) > 1:\n",
    "            # print(ll)\n",
    "            flag = index = 0\n",
    "            for i in range(len(ll)):\n",
    "                if ll[i][1] >0:\n",
    "                    if ans == \"\":\n",
    "                        ans += ll[i][0]\n",
    "                        ll[i][1] -= 1\n",
    "                        flag = 1\n",
    "                    else:\n",
    "                        if ll[i][0] != ans[-1]:\n",
    "                            ans += ll[i][0]\n",
    "                            ll[i][1] -= 1\n",
    "                            flag = 1\n",
    "                if flag:\n",
    "                    index = i\n",
    "                    break\n",
    "            while flag and i+1 < len(ll):\n",
    "                if ll[i][1] < ll[i+1][1]:\n",
    "                    ll[i],ll[i+1] = ll[i+1],ll[i]\n",
    "                    i += 1\n",
    "                else:\n",
    "                    break\n",
    "        index = 0\n",
    "        for i in range(len(ll)):\n",
    "            if ll[i][1] > 0:\n",
    "                index= i\n",
    "                break\n",
    "        # print(ans)\n",
    "        if ll[index][1] > 1 or ans[-1] == ll[index][0]:\n",
    "            return \"\"\n",
    "        ans += ll[index][0]\n",
    "        if len(ans) != n:\n",
    "            return \"\"\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reorganizeString(self, s: str) -> str:\n",
    "        # 先放出现最多的，然后隔开它！\n",
    "        c = Counter(s)\n",
    "        lst = list(c.items())\n",
    "        lst = [(y, x) for x, y in lst]\n",
    "        from sortedcontainers import SortedList\n",
    "        stl = SortedList(lst)\n",
    "        ans = ''\n",
    "        while stl:\n",
    "            #print(ans, stl)\n",
    "            if not ans or ans[-1] != stl[-1][1]: # 可以直接加\n",
    "                cnt, ch = stl[-1]\n",
    "                ans += ch\n",
    "                del stl[-1]\n",
    "                if cnt == 1:\n",
    "                    continue\n",
    "                else:\n",
    "                    stl.add((cnt - 1, ch))\n",
    "            else:\n",
    "                if len(stl) == 1:\n",
    "                    return ''\n",
    "                cnt, ch = stl[-2]\n",
    "                ans += ch\n",
    "                del stl[-2]\n",
    "                if cnt == 1:\n",
    "                    continue\n",
    "                else:\n",
    "                    stl.add((cnt - 1, ch))\n",
    "        return ans\n",
    "                \n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import Counter\n",
    "from sortedcontainers import SortedList\n",
    "class Solution:\n",
    "    def reorganizeString(self, s: str) -> str:\n",
    "        cnt = Counter(s)\n",
    "        n = len(s)\n",
    "        limit = n//2 + 1 if n%2 else n//2\n",
    "        x = max(list(cnt.values()))\n",
    "        if x > limit:\n",
    "            return \"\"\n",
    "        a = SortedList([[k, v] for k, v in cnt.items()], key = lambda x: x[1])\n",
    "        ans = \"\"\n",
    "        i = 0\n",
    "        for i in range(0, n, 2):\n",
    "            #print(a)\n",
    "            x = a.pop()\n",
    "            if i < n-1:\n",
    "                y = a.pop(0) \n",
    "            else:\n",
    "                y = [\"\", 0]  \n",
    "            if ans and x[0] == ans[-1]:\n",
    "                ans += (y[0]+x[0])\n",
    "            else:       \n",
    "                ans += (x[0]+y[0])\n",
    "\n",
    "            x[1] -= 1\n",
    "            y[1] -= 1\n",
    "            if x[1] > 0:\n",
    "                a.add(x)\n",
    "            if y[1] > 0:\n",
    "                a.add(y)\n",
    "        return ans\n",
    "\n",
    "\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reorganizeString(self, s: str) -> str:\n",
    "        if len(s)<2:\n",
    "            return s\n",
    "        ans=[\"\"]*len(s)\n",
    "        \n",
    "        length=len(s)\n",
    "        counts=collections.Counter(s)\n",
    "        maxCount=max(counts.items(),key=lambda x:x[1])[1]\n",
    "        if maxCount>(length+1)//2:\n",
    "            return \"\"\n",
    "        \n",
    "        evenindex,oddindex=0,1\n",
    "        halfLength=length//2\n",
    "\n",
    "        for c,count in counts.items():\n",
    "            while count>0 and count<=halfLength and oddindex<length:\n",
    "                ans[oddindex]=c\n",
    "                count-=1\n",
    "                oddindex+=2\n",
    "            while count>0:\n",
    "                ans[evenindex]=c\n",
    "                count-=1\n",
    "                evenindex+=2\n",
    "        return \"\".join(ans)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import Counter\n",
    "from heapq import *\n",
    "\n",
    "class Solution:\n",
    "    def reorganizeString(self, s: str) -> str:\n",
    "        if not s: return ''\n",
    "\n",
    "        char_to_freq = Counter(s)\n",
    "        max_heap = [(-freq, char) for char, freq in char_to_freq.items()]\n",
    "        heapq.heapify(max_heap)\n",
    "\n",
    "        prev_char, prev_freq = None, 0\n",
    "        res = []\n",
    "\n",
    "        while max_heap:\n",
    "            freq, char = heappop(max_heap)\n",
    "            res.append(char)\n",
    "\n",
    "            if prev_freq < 0:\n",
    "                heappush(max_heap, (prev_freq, prev_char))\n",
    "\n",
    "            prev_char, prev_freq = char, freq + 1\n",
    "        \n",
    "        if len(res) != len(s):\n",
    "            return ''\n",
    "        return ''.join(res)\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reorganizeString(self, s: str) -> str:\n",
    "        if len(s) < 2:\n",
    "            return s\n",
    "        \n",
    "        length = len(s)\n",
    "        counts = collections.Counter(s)\n",
    "        maxCount = max(counts.items(), key=lambda x: x[1])[1]\n",
    "        if maxCount > (length + 1) // 2:\n",
    "            return \"\"\n",
    "        \n",
    "        queue = [(-x[1], x[0]) for x in counts.items()]\n",
    "        heapq.heapify(queue)\n",
    "        res = list()\n",
    "\n",
    "        while len(queue) > 1:\n",
    "            _, letter1 = heapq.heappop(queue)\n",
    "            _, letter2 = heapq.heappop(queue)\n",
    "            res.extend([letter1, letter2])\n",
    "            counts[letter1] -= 1\n",
    "            counts[letter2] -= 1\n",
    "            if counts[letter1] > 0:\n",
    "                heapq.heappush(queue, (-counts[letter1], letter1))\n",
    "            if counts[letter2] > 0:\n",
    "                heapq.heappush(queue, (-counts[letter2], letter2))\n",
    "        \n",
    "        if queue:\n",
    "            res.append(queue[0][1])\n",
    "        \n",
    "        return \"\".join(res)"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
